package org.chnxi.study.datastructrues.doublelinkedlist;

/**
 * 双向链表：
 * 双向链表的遍历、添加、修改和删除的思路
 * 1、遍历方向和单向链表一样，只是可以向前，也可以向后；
 * 2、添加（默认添加到双向链表的最后）
 *     1）先找到双向链表的最后节点；
 *     2）temp.next = newHeroNode;
 *     3）newHeroNode.pre = temp;
 * 3、修改思路和原理同单向链表一样；
 * 4、删除
 *     1）因为是双向链表，因此，我们可以实现自我删除某个节点；
 *     2）直接找到要删除的节点，例如：temp；
 *     3）temp.pre.next = temp.next;
 *     4）temp.next.pre = temp.pre;
 * @param <T>
 */
public class DoubleLinkedLis<T> {

    //先初始化一个头结点，不存放具体的数据
    private Node<T> head = new Node<T>(null);

    /**
     * 返回头节点
     * @return
     */
    public Node<T> getHead(){
        return head;
    }

    public void add(T t){
        //遍历链表找到最后
        Node<T> tmp = head;
        while(true){
            //此时到达最后
            if(tmp.next == null){
                break;
            }
            tmp = tmp.next;
        }
        //在链表最后加入新节点，行程双向链表
        Node newNode = new Node(t);
        tmp.next = newNode;
        newNode.pre = tmp;
    }

    public void add(int idx , T t){
        Node<T> newNode = new Node(t);
        Node<T> tmp = head;
        for(int i = 0 ; i <= idx ; i++){
            if(tmp == null){
                throw new IllegalArgumentException("idx超出链表长度，不能添加");
            }
            if(i == idx){
                newNode.next = tmp.next;
                newNode.pre = tmp;
                tmp.next = newNode;
                break;
            }
            tmp = tmp.next;
        }
    }

    /**
     * 修改一个节点内容，与单向链表方式一致
     * @param t
     * @return
     */
    public boolean update(T t){
        if(head.next == null){
            System.out.println("链表为空，不能修改");
            return false;
        }

        Node<T> tmp = find(t);

        //链表中不存在该节点，直接返回
        if(tmp == null){
            System.out.println("链表中未找到该节点，不能修改");
            return false;
        }
        tmp.t = t;
        return true;
    }

    public boolean delete(T t){

        if(head.next == null){
            System.out.println("链表为空，不能删除");
            return false;
        }

        Node<T> tmp = find(t);

        //链表中不存在该节点，直接返回
        if(tmp == null){
            System.out.println("链表中未找到该节点，不能修改");
            return false;
        }

        tmp.pre.next = tmp.next;
        //删除的在最后时，不需要执行
        if(tmp.next != null) {
            tmp.next.pre = tmp.pre;
        }
        return false;
    }

    protected Node<T> find(T t){
        if(t == null){
            return null;
        }

        Node<T> tmp = head.next;
        boolean isfind = false;
        while (true){
            //遍历完成后未找到节点
            if(tmp == null){
                break;
            }
            if( tmp.t == t || (tmp.t!= null && tmp.t.equals(t))){
                isfind = true;
                break;
            }
            tmp = tmp.next;
        }
        //链表中不存在该节点，直接返回
        if(!isfind){
            System.out.println("链表中未找到该节点");
            return null;
        }

        return tmp;
    }

    public void printList(){
        Node<T> tmp = head.next;
        while(true){
            if(tmp == null){
                break;
            }
            System.out.println(tmp.t);
            tmp = tmp.next;
        }
    }

}

class Node<T>{
    T t;
    //指向前一个节点
    Node<T> pre;
    //指向下一个节点
    Node<T> next;

    public Node(T t){
        this.t = t;
    }
}